/**
 * 插入排序
 * 已排序区间、未排序区间
 * 从未排序区间取一个值，放入已排序区间
 * 保持已排序区间是有序状态
 * 精髓在于 从有序区间里从后往前找到合适位置插入
 */

export {};

function insertSort(arr: number[]): number[] {
  for (let i = 1; i < arr.length; i++) {
    let value = arr[i];

    let j = i - 1;
    for (; j >= 0; j--) {
      if (arr[j] > value) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }

    arr[j + 1] = value;
  }

  return arr;
}

console.log(insertSort([6, 5, 1, 2, 4, 3]));
